﻿namespace LeetCodeProject._0001_1000._001_100._81_90._081;

public class Solution
{
    public bool Search(int[] nums, int target)
    {
        if (nums == null || nums.Length == 0)
            return false;
        return Search(nums, 0, nums.Length - 1, target);
    }

    private bool Search(int[] nums, int low, int high, int target)
    {
        while (low <= high)
        {
            var mid = low + (high - low) / 2;
            if (nums[mid] == target)
                return true;
            if (low < mid - 1 && nums[low] < nums[mid - 1])
            {
                if (nums[low] <= target && target <= nums[mid - 1])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            else if (mid + 1 < high && nums[mid] < nums[high])
            {
                if (nums[mid] <= target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            else
            {
                return Search(nums, low, mid - 1, target) || Search(nums, mid + 1, high, target);
            }
        }

        return false;
    }
}